// https://www.lintcode.com/problem/interleaving-string/

public class Solution {
    /**
     * @param s1: A string
     * @param s2: A string
     * @param s3: A string
     * @return: Determine whether s3 is formed by interleaving of s1 and s2
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        // write your code here
        return _isInterleave(s3, 0, s1, 0, s2, 0);
    }
    
    private boolean _isInterleave(String s3, int s3_start, String s1, int s1_start, String s2, int s2_start) {
        if ((s3_start == s3.length()) && (s1_start == s1.length()) && (s2_start == s2.length())) {
            return true;
        }
        if ((s1_start < s1.length()) && (s3.charAt(s3_start) == s1.charAt(s1_start))) {
            if (_isInterleave(s3, s3_start + 1, s1, s1_start + 1, s2, s2_start)) {
                return true;
            }
        }
        if ((s2_start < s2.length()) && (s3.charAt(s3_start) == s2.charAt(s2_start))) {
            if (_isInterleave(s3, s3_start + 1, s1, s1_start, s2, s2_start + 1)) {
                return true;
            }
        }
        return false;
    }
}